Thus, we verify that the random effects estimator is equivalent to the generative model (1). Specifically, if u(x) = 1 for all x X, we use ( X, P,ψ) for simplicity. Due to the separability of ψ, we have the following coreset definition. Definitions 2.2 and 2.3, the regression objectives of OLSE and GLSE can be decomposed into Thus, we can apply the above definition to define coresets for OLSE and GLSE. Now we are ready to describe the FL framework in the language of a query space. We first prove Theorem C.1 and propose the corresponding algorithm that constructs an Next, we prove Theorem C.2 and propose the corresponding algorithm that constructs an accurate Caratheodory's Theorem, there must exist at most To accelerate the running time, Jubran et al. [ By the Caratheodory's Theorem, there must exist at most In this section, we complete the proofs for GLSE.

Empirical risk minimization (ERM) may be used to generalize the result from train to test data.

Open source code and experiments are also provided.

A.1 The Feldman-Langberg framework We first give the definition of query space and the corresponding coresets. Specifically, if u(x) = 1 for all x X, we use ( X, P,f) for simplicity. Due to the separability of f, we have the following coreset definition. Then by Definition A.2, Lemma 4.4 represents that Now we are ready to give the Feldman-Langberg framework. We also introduce a notion which measures the combinatorial complexity of a query space.

A.1 The Feldman-Langberg framework We first give the definition of query space and the corresponding coresets. Specifically, if u(x) = 1 for all x X, we use ( X, P,f) for simplicity. Due to the separability of f, we have the following coreset definition. Then by Definition A.2, Lemma 4.4 represents that Now we are ready to give the Feldman-Langberg framework. We also introduce a notion which measures the combinatorial complexity of a query space.

We apply the discrepancy method and a chaining approach to give improved bounds on the coreset complexity of a wide class of kernel functions. Our results give randomized polynomial time algorithms to produce coresets of size $O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$ for the Gaussian and Laplacian kernels in the case that the data set is uniformly bounded, an improvement that was not possible with previous techniques. We also obtain coresets of size $O\big(\frac{1}{\varepsilon}\sqrt{\log\log \frac{1}{\varepsilon}}\big)$ for the Laplacian kernel for $d$ constant. Finally, we give the best known bounds of $O\big(\frac{\sqrt{d}}{\varepsilon}\sqrt{\log(2\max\{1,\alpha\})}\big)$ on the coreset complexity of the exponential, Hellinger, and JS Kernels, where $1/\alpha$ is the bandwidth parameter of the kernel.

Radial basis function neural networks (\emph{RBFNN}) are {well-known} for their capability to approximate any continuous function on a closed bounded set with arbitrary precision given enough hidden neurons. In this paper, we introduce the first algorithm to construct coresets for \emph{RBFNNs}, i.e., small weighted subsets that approximate the loss of the input data on any radial basis function network and thus approximate any function defined by an \emph{RBFNN} on the larger input data. In particular, we construct coresets for radial basis and Laplacian loss functions. We then use our coresets to obtain a provable data subset selection algorithm for training deep neural networks. Since our coresets approximate every function, they also approximate the gradient of each weight in a neural network, which is a particular function on the input. We then perform empirical evaluations on function approximation and dataset subset selection on popular network architectures and data sets, demonstrating the efficacy and accuracy of our coreset construction.